1. Field of the Invention
This invention relates generally to the reduction of redeye in digital images, and specifically to the identification and correction of redeye regions within a digital image.
2. Description of the Related Art
Redeye occurs when a flash positioned near the lens of a camera enters the pupils of a subject's eyes, and then bounces off the eye's blood-rich retinal membranes back to the camera. The resultant image may now have a redeye effect, namely the image of the pupil of the eye appears to be unnaturally red. The redness can be mitigated through optical means or through digital processing.
Although most cameras attempt to reduce it, the “redeye” effect appears in many photographs. At the instant the photo is taken, bright light from the flash enters the eye through the pupil and reflects off the retina (the back of the eye) to the camera. The unwanted reflection leaves the subject with unnaturally red, glowing eyes.
In most redeye photos, the effect conforms to the following description. The sclera (the white part) is not affected. The iris (colored part) of the eye is not affected. The cornea (the clear part in front of the pupil) is not affected. Although this portion of the eye is clear, a small reflection of the flash from the cornea leaves a natural looking ‘glint’ in the eye. This glint is superimposed over the pupil. The pupil (the hole in the eye that one sees through) is affected. Instead of appearing dark or black, the pupil is red and luminescent. Regardless of whether the pupil is red or black, the glint in the cornea is visible as a very light area within the pupil.
In digital photos, because the precision of focus and resolution of display are not infinite (and may indeed be very poor), the redeye-affected region may spill over to the regions immediately adjacent to the pupil. This region of blending usually extends one or two pixels out of the pupil, but can be greater, especially if the picture has been blown up to a size greater than its resolution allows for.
The reduction or elimination of redeye can be attempted while the photograph is being taken or after it has been taken. The common approach for redeye reduction adopted in cameras is usually the following: a pre-flash is made before the photo is actually taken, thereby conditioning the eye to lessen the opening size of the pupil diameter. Therefore when the flash of the actual photograph goes off, the reflection of the retina is not so noticeable. Positioning of the flash well above the camera lens can also mitigate the redeye effect. Regardless of whether precaution against redeye was taken by the photographer, redeye may still end up in the resulting picture. Indeed, there are many photos in circulation today that would benefit from the removal of redeye. Therefore, it is valuable to discuss the removal of redeye from a photo after it has been taken.
The technique to remove redeye from a photo involves two phases: redeye pupil location and color replacement. In the redeye pupil location phase, the pupil or pupils exhibiting the redeye effect are found. In the color replacement phase, the color of the pupil or pupils is changed so that they look more like ordinary pupils than redeye pupils.
Pupil location is the more interesting and difficult problem. It can be accomplished manually or automatically. Manual pupil location requires that the user identify the problem region. Automatic pupil location is very difficult to reliably ensure due to possible interference or confusion from other parts of the image. An example of automatic pupil location is shown in U.S. Pat. No. 6,151,403. A reasonable balance between fully manual and fully automatic pupil location is automatic detection within a manually selected area of interest. This allows the user to crop out any confusing areas of the photo so that the automatic redeye detector can more easily find the elusive pupil or pupils. Examples of redeye reduction are found in the following U.S. Pat. Nos.: 6,134,339; 6,160,923; 6,009,209; 5,596,346; and 5,432,863.
The success of different redeye reduction techniques varies more in the pupil location algorithm than in the color replacement. Poor color replacement may leave the image looking scarcely better than it had before the touch-up. Poor pupil location will surely make the image look worse. Location of the pupil is also more time consuming than color replacement. Speed is crucial to good pupil location.
U.S. Pat. No. 6,016,354 to Lin et al., incorporated herein by reference, presents the following scheme for redeye reduction. The user selects a small rectangular section of a digital image within which lies at least one redeye pupil. A threshold is applied to the pixels within that section so that pixels with a value above the threshold are considered as candidate redeye pixels and those below are ignored (the threshold is applied to a measure of redeye likelihood, not just the pixels' R value). A pupil search is conducted on the candidate pixels. This search yields the largest circular collection of pixels with the highest concentration of candidate pixels by least squares. Some extra work addresses the issue of the pupil found containing no more and no less than the entire instance of that redeye pupil. Each pixel in the pupil is replaced with a gray value with 70% of the original's luminescence. This attempts to preserve the pupil's glint while leaving it with a more natural color.
Adobe's Photo Deluxe© Business edition has a redeye reduction function that works quite effectively and has a good balance between speed of execution and effectiveness. While the underlying algorithm details are not known to the Applicant, the following observations were made: (a) it uses the same input as required by Lin et al., (b) the pupil location algorithm seems to be different than the method of Lin et al. in that it appears faster and it attempts to find a second pupil after it finds the first. Its color replacement produces similar results as Lin et al. The pupil is close to its proper color and the glint appears nearly as bright as it should be.
However, both have drawbacks. Redeye correction is difficult, and nobody does a spotless job. Therefore, the best redeye algorithm is that with the fewest faults. Applicant examined various faults that occur in redeye algorithms. These can be categorized as qualitative and quantitative faults in results, and speed issues. It seems difficult to imagine an algorithm requiring significantly less space for operation since the entire input rectangle must be in memory at once.
The algorithm of Lin et al. required h*w*log(min(h,w)) time for pupil location where h and w are the sides of the input rectangle. Photo Deluxe© uses about the same amount of time. It achieves an almost instantaneous result with a small input rectangle, but slows down significantly with larger ones and ultimately pops up a warning dialogue box if the input is huge. Because it is likely that the instance of redeye fits within a small rectangle, this behavior isn't of much concern. It would be nice, however, to find an algorithm that is linear in time with respect to n, defined as h*w. This algorithm would go over each pixel in the input a constant number of times before deciding where the pupils are.
For the term “quantitative faults” to have any meaning in terms of results, it must be defined. We will call failure to locate a redeye pupil a quantitative error in a redeye correction algorithm. Also, redeye software that mistakenly locates an area as redeye will be said to have a quantitative fault in its result. Because all techniques will be susceptible to some sort of error in this area, “improvement” may not be a hard and fast term. Lin et al. have two major faults here.
Adobe's Photo Deluxe© not only is able to reduce the redeye effect like the algorithm of Lin et al. but it also attempts to find a second eye. Unfortunately, in cases where only one redeye pupil is in the input rectangle (or when it fails to find an existing second pupil), an unwanted circle is declared a redeye pupil and corrected as such, leaving an unsightly circular blotch of gray on a pimple or a red earring, or other image having round red characteristics.
Qualitative faults in results encompass poor replacement color or strategy, unnecessary obscuring of the pupil's glint, or lack of versatility in high/low brightness/contrast situations. Both Lin et a. and Adobe Photo Deluxe©, seem to do a sub-optimal job of preserving the pupil's glint. Each algorithm comes up with a solid circular area (encompassing this glint) to darken and gray. The shine is preserved at all by the fact that the pupil is not darkened too much. Unfortunately, this can sometimes be noticed when the pupil is not quite dark enough to look real. A better color replacement algorithm is needed. Preferably one that would leave the glint alone and darken only the red pupil area.